home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / TGA2GIF.ZIP / TGA2GIF.C
Encoding:
C/C++ Source or Header  |  1993-10-13  |  46.0 KB  |  1,980 lines
  1. /*
  2.    tga2gif -- convert type 2 Targa (tga) files to .gif files
  3.  
  4.     Copyright 1991 Stephen B. Coy
  5.          All Rights Reserved
  6.  
  7.          Distribute freely.
  8.  
  9.    9/92 Mods by Drew Wells to convert Targa instead of Vivid .img format
  10.    9/93 Mods by Chris Cason to allow operation under VMS and other O/S's
  11.         Other OS users - be sure to set PATH_SEPARATOR appropriately
  12.         You may have to do other things as well.
  13. */
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <ctype.h>
  19.  
  20. #ifdef VMS
  21. #include <unixio.c>
  22. #pragma message disable IMPLICITFUNC        /* helps with OpenVMS C           */
  23. #define PATH_SEPARATOR  ']'                 /* define this for VMS            */
  24. #endif
  25.  
  26. #ifdef MSDOS
  27.     #define READ_MODE       "rb"
  28.     #define WRITE_MODE      "wb"
  29. #else
  30.     #define READ_MODE       "r"
  31.     #define WRITE_MODE      "w"
  32. #endif
  33.  
  34. #ifndef PATH_SEPARATOR
  35. #define PATH_SEPARATOR            '\\'
  36. #endif
  37.  
  38. #ifndef MIN
  39. #define MIN(a,b)        ((a)<(b)?(a):(b))
  40. #endif
  41. #ifndef MAX
  42. #define MAX(a,b)        ((a)>(b)?(a):(b))
  43. #endif
  44.  
  45. #define CLIP(x) ((x)>255?255:((x)<0?0:(x)))
  46.  
  47. #define PRINT_STEP      (16)
  48.  
  49. #define RES             (64)
  50. #define DEF_NOISE       (8)
  51.  
  52. /* color palette selection methods */
  53. #define POP             (0)
  54. #define MEDIAN_BOX      (1)
  55. #define FIXED           (2)
  56. #define PAL_FILE        (3)
  57.  
  58. #define COUNT_LIMIT     (0xffffL)
  59.  
  60. /*
  61.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  62.  */
  63. typedef int             code_int;
  64.  
  65. /*
  66.  * Pointer to function returning an int
  67.  */
  68. typedef int (* ifunptr)();
  69.  
  70. #ifdef SIGNED_COMPARE_SLOW
  71. typedef unsigned long int count_int;
  72. typedef unsigned short int count_short;
  73. #else
  74. typedef long int          count_int;
  75. #endif
  76.  
  77.  
  78. /*** Function Prototypes ***/
  79.  
  80. static Putword( int w, FILE *fp );
  81. static output( code_int code );
  82. static cl_block ();
  83. static cl_hash(register count_int hsize);
  84. static writeerr();
  85. static char_init();
  86. static char_out( int c );
  87. static flush_char();
  88.  
  89.  
  90. int     fake_eof = 0;
  91.  
  92. long    count_limit = COUNT_LIMIT;      /* limit pixel count to this */
  93.  
  94. typedef struct box {
  95.         int     r0, r1, g0, g1, b0, b1;
  96.         long    rave, gave, bave;
  97.         long    count;
  98. } Box;
  99.  
  100. typedef struct node {
  101.     unsigned short  color;
  102.     unsigned short  count;  /* doubles as pixel count & palette index */
  103.     struct node     *next;
  104. } Node;
  105.  
  106. Node    *grid[RES][RES];        /* linked list headers for each red/green pair */
  107.  
  108. int     red[256], grn[256], blu[256];           /* 6 bit palette */
  109. int     red8[256], grn8[256], blu8[256];        /* 8 bit for gif */
  110.  
  111. FILE    *infp, *palfp;
  112.  
  113. unsigned long   total_pixels = 0,
  114.         total_colors = 0;
  115.  
  116.   int     width, height,
  117.     noise = 0,              /* default to no noise */
  118.     method = POP,           /* default to pop */
  119.     ordered = 0,            /* do ordered dither */
  120.     fixed_pal = 0,          /* default fixed palette */
  121.     save_pal = 0,           /* save palette to file? */
  122.     last_pass = 0;          /* to help with out of RAM conditions */
  123.   int             xres, yres;             /* image size */
  124.  
  125. int     ord_dith[4][4] = {{-7,  1, -5,  3},
  126.               { 5, -3,  7, -1},
  127.               {-4,  4, -6,  2},
  128.               { 8,  0,  6, -2}};
  129.  
  130. char *strlwr (char *s)
  131. {
  132.   char        *_s = s ;
  133.  
  134.   while (*s)
  135.   {
  136.     *s = tolower (*s) ;
  137.     s++ ;
  138.   }
  139.   return (_s) ;
  140. }
  141.  
  142. main(ac, av)
  143.     int     ac;
  144.     char    **av;
  145. {
  146.     int     i, w, h, c, r, g, b;
  147.     long    total;
  148.     char    file[80],       /* root of file name */
  149.         infile[80],     /* input file name */
  150.         outfile[80],    /* gif file name */
  151.         palfile[80],    /* palette file name */
  152.         name[80];       /* name of file as run from av[0] */
  153.     int     (*grab_a_pix)(), get_pix(), get_pix_fs();
  154.  
  155.         strcpy(name, strrchr(av[0], PATH_SEPARATOR)+1); /* get rid of the path */
  156.         *strchr(name, '.') = 0;                         /* get rid of the .exe */
  157.         strlwr(name);                                   /* gimmee lower case */
  158.  
  159.     palfile[0] = 0;         /* NULL string */
  160.  
  161.     grab_a_pix = get_pix;   /* default, non dithered function for gif */
  162.     if(ac < 2)
  163.         usage(name);
  164.     infile[0] = '\0';
  165.     for(i=1; i<ac; i++) {   /* loop through command line args */
  166.         strlwr(av[i]);
  167.         if(av[i][0] != '-') {   /* must be file name */
  168.             strcpy(file, av[i]);
  169.             strcpy(infile, av[i]);
  170.          strcpy(outfile, av[i]);
  171.          strcat(infile, ".tga");
  172.             strcat(outfile, ".gif");
  173.         } else {
  174.             switch(av[i][1]) {
  175.                 case 'd':
  176.                     grab_a_pix = get_pix_fs;
  177.                     break;
  178.                 case 'f':
  179.                     method = FIXED;
  180.                     if(isdigit(av[i+1][0])) {
  181.                         fixed_pal = atoi(av[i+1]);
  182.                         i++;
  183.                     }
  184.                     break;
  185.                 case 'm':
  186.                     method = MEDIAN_BOX;
  187.                     if(isdigit(av[i+1][0])) {
  188.                         count_limit = atoi(av[i+1]);
  189.                         i++;
  190.                     }
  191.                     break;
  192.                 case 'o':
  193.                     ordered = 1;
  194.                     break;
  195.                 case 'p':
  196.                     i++;
  197.                     strcpy(palfile, av[i]);
  198. /*                    if(access(palfile, 0) == 0) { */  /* if file exists */
  199. /*                        method = PAL_FILE; */
  200. /*                    } else { */
  201.                         save_pal = 1;
  202. /*                    } */
  203.                     break;
  204.                 case 'r':
  205.                     srand(1962);
  206.                     noise = DEF_NOISE;
  207.                     if(isdigit(av[i+1][0])) {
  208.                         noise = atoi(av[i+1]);
  209.                         i++;
  210.                     }
  211.                     break;
  212.                 default:
  213.                     fprintf(stderr, "Error, unknown flag %s\n", av[i]);
  214.                     usage(name);
  215.                     break;
  216.             }
  217.         }
  218.     }       /* end of i loop through args */
  219.  
  220.   /* Open image file for reading */
  221.   infp = fopen(infile, READ_MODE);
  222.     if(!infp) {
  223.         fprintf(stderr, "Error opening file %s for input.\n", infile);
  224.         exit(1);
  225.     }
  226.  
  227.   /*
  228.         Read targa header. 3rd byte should be 2 signifying a
  229.         type 2 targa file.  Get resolution.
  230.     */
  231.  
  232.     my_getc(infp);
  233.     my_getc(infp);
  234.     if(my_getc(infp) != 2) {
  235.       fprintf(stderr, "Sorry, but this program only works for type 2 Targa files.\n");
  236.         exit(1);
  237.     }
  238.     for(i=3; i<12; i++) {
  239.         my_getc(infp);
  240.     }
  241.     /* get res */
  242.     xres = my_getc(infp);
  243.     xres += my_getc(infp)<<8;
  244.     yres = my_getc(infp);
  245.     yres += my_getc(infp)<<8;
  246.     /* get last two bytes of the header */
  247.     my_getc(infp);
  248.     my_getc(infp);
  249.     printf("image size : %d x %d\n", xres, yres);
  250.  
  251.  
  252.   /* Put width of image in w */
  253.   w = xres;
  254.   width = w;
  255.   /* Put height of image in h */
  256.   h = yres;
  257.   height = h;
  258.  
  259.     /* read in image and build tree if we need to */
  260.  
  261.     if(method==POP || method==MEDIAN_BOX) {
  262.         printf("Building tree.\n        total colors = ");
  263.         total_pixels = total_colors;
  264.         total = (long)w * (long)h;
  265.         while(total > 0) {
  266.       /* Read color run length */
  267.             c = 1;
  268.             if(c==0)
  269.                 c = 1024;
  270.  
  271.       /* read an rgb triple */
  272.             b = my_getc(infp);
  273.             g = my_getc(infp);
  274.             r = my_getc(infp);
  275.  
  276.             add_color(r>>2, g>>2, b>>2, c);         /* add to tree */
  277.             total -= c;
  278.             if(total_pixels != total_colors) {
  279.                 if((total_colors % (PRINT_STEP<<2)) == 0)
  280.                     printf("%8ld\b\b\b\b\b\b\b\b", total_colors);
  281.                 total_pixels = total_colors;
  282.             }
  283.         }
  284.         printf("%8ld\b\b\b\b\b\b\b\b", total_colors);
  285.         printf("\n");
  286.     }
  287.  
  288.     switch(method) {
  289.         case POP        : pop();        break;
  290.         case MEDIAN_BOX : m_box();      break;
  291.         case FIXED      : fixed();      break;
  292.         case PAL_FILE   :
  293.             if((palfp = fopen(palfile, "r")) == NULL) {
  294.                 fprintf(stderr, "Error opening file %s for reading palette.\n", palfile);
  295.                 exit(1);
  296.             }
  297.             printf("Reading palette from %s\n", palfile);
  298.             for(i=0; i<256; i++) {
  299.                 fscanf(palfp, "%d %d %d", &red8[i], &grn8[i], &blu8[i]);
  300.             }
  301.             fclose(palfp);
  302.             break;
  303.         default : fprintf(stderr, "No palette selection method chosen.\n");
  304.             break;
  305.     }
  306.  
  307.     /* fix palette entries for gif encoding */
  308.  
  309.     if(method != PAL_FILE) {
  310.         for(i=0; i<256; i++) {
  311.             red8[i] = red[i]*255, red8[i] /= 63;
  312.             grn8[i] = grn[i]*255, grn8[i] /= 63;
  313.             blu8[i] = blu[i]*255, blu8[i] /= 63;
  314.         }
  315.         if(method == FIXED && fixed_pal == 0)   /* grey */
  316.             for(i=0; i<256; i++) {
  317.                 red8[i] = i;
  318.                 grn8[i] = i;
  319.                 blu8[i] = i;
  320.             }
  321.         if(save_pal) {
  322.             if((palfp = fopen(palfile, "w")) == NULL) {
  323.                 fprintf(stderr, "Error opening file %s for writing palette.\n", palfile);
  324.                 exit(1);
  325.             }
  326.             printf("Writing palette to %s\n", palfile);
  327.             for(i=0; i<256; i++) {
  328.                 fprintf(palfp, "%d %d %d\n", red8[i], grn8[i], blu8[i]);
  329.             }
  330.             fclose(palfp);
  331.         }
  332.     } else {        /* else if method == PAL_FILE */
  333.         for(i=0; i<256; i++) {
  334.             red[i] = red8[i]>>2;
  335.             grn[i] = grn8[i]>>2;
  336.             blu[i] = blu8[i]>>2;
  337.         }
  338.     }
  339.  
  340.     if(method==POP || method==MEDIAN_BOX)
  341.         remap_all();    /* remap all the tree elements to the palette */
  342.  
  343.     /* 2nd pass through image */
  344.  
  345.     fclose(infp);
  346.  
  347.   /* Open image and skip header info since we read it before */
  348.     infp = fopen(infile, "rb");
  349.  
  350.     fake_eof = 0;                /* reset fake end of file pointer */
  351.     if(!infp) {
  352.         fprintf(stderr, "Error opening file %s for 2nd pass input.\n", infile);
  353.         exit(1);
  354.     }
  355.   /* skip header info */
  356.   my_getc(infp);
  357.     my_getc(infp);
  358.     my_getc(infp);
  359.     for(i=3; i<12; i++) {
  360.         my_getc(infp);
  361.     }
  362.   /* resolution */
  363.     my_getc(infp);
  364.     my_getc(infp);
  365.     my_getc(infp);
  366.     my_getc(infp);
  367.     /* get last two bytes of the header */
  368.     my_getc(infp);
  369.     my_getc(infp);
  370.  
  371.     last_pass = 1;
  372.  
  373.     printf("GIF encoding in progress.\n");
  374.  
  375.     GIFEncode(outfile,        /* file name */
  376.         w, h,                   /* image size */
  377.         0,                      /* no interlace */
  378.         0,                      /* bkg color */
  379.         8,                      /* bits per pixel */
  380.         red8, grn8, blu8,       /* palette arrays */
  381.         grab_a_pix);            /* pixel function */
  382.  
  383.     fclose(infp);
  384.  
  385. }       /* end of img2gif */
  386.  
  387. my_getc(FILE *fp)
  388. {
  389.     int     c;
  390.  
  391.     if(fake_eof) {
  392.         return 0;
  393.     } else {
  394.         c = getc(fp);
  395.         if(c == EOF) {
  396.             fake_eof = 1;
  397.             return 0;
  398.         }
  399.         return c;
  400.     }
  401. }
  402.  
  403. #define SWAP(a, b)    { unsigned int   tmp;            \
  404.             tmp = a; a = b; b = tmp; }
  405.  
  406. /*
  407.     pop -- choose the best colors by picking the most popular
  408. */
  409.  
  410. pop()
  411. {
  412.     int             i, r, g;
  413.     Node            *ptr;
  414.     unsigned int    pal[256];
  415.  
  416.     printf("Choosing palette by popularity.\n");
  417.     for(i=0; i<256; i++)
  418.         pal[i] = 0;
  419.  
  420.     /* force corners of rgb color cube out of the running */
  421.     add_color( 0,  0,  0, 0);
  422.     add_color(63,  0,  0, 0);
  423.     add_color( 0, 63,  0, 0);
  424.     add_color( 0,  0, 63, 0);
  425.     add_color(63, 63,  0, 0);
  426.     add_color( 0, 63, 63, 0);
  427.     add_color(63,  0, 63, 0);
  428.     add_color(63, 63, 63, 0);
  429.  
  430.     /* force feed the corners into the palette */
  431.     red[0] =  0; grn[0] =  0; blu[0] =  0;
  432.     red[1] = 63; grn[1] =  0; blu[1] =  0;
  433.     red[2] =  0; grn[2] = 63; blu[2] =  0;
  434.     red[3] =  0; grn[3] =  0; blu[3] = 63;
  435.     red[4] = 63; grn[4] = 63; blu[4] =  0;
  436.     red[5] =  0; grn[5] = 63; blu[5] = 63;
  437.     red[6] = 63; grn[6] =  0; blu[6] = 63;
  438.     red[7] = 63; grn[7] = 63; blu[7] = 63;
  439.  
  440.     for(r=0; r<RES; r++)
  441.         for(g=0; g<RES; g++) {
  442.             ptr = grid[r][g];
  443.             while(ptr) {
  444.                 if(ptr->count > pal[255]) {
  445.                     pal[255] = ptr->count;
  446.                     red[255] = r;
  447.                     grn[255] = g;
  448.                     blu[255] = ptr->color;
  449.  
  450.                     i = 255;        /* bubble up */
  451.                     while(pal[i]>pal[i-1] && i>8) {
  452.                         SWAP(pal[i], pal[i-1]);
  453.                         SWAP(red[i], red[i-1]);
  454.                         SWAP(grn[i], grn[i-1]);
  455.                         SWAP(blu[i], blu[i-1]);
  456.                         i--;
  457.                     }
  458.                 }
  459.                 ptr = ptr->next;        /* move to next color */
  460.             }       /* end of current chain */
  461.         }       /* end of r loop */
  462. }       /* end of pop */
  463.  
  464.  
  465. /*
  466.     fixed() -- use a fixed palette
  467.            0 == grey scale
  468.            1 == 8x8x4
  469.            2 == 6x7x6
  470. */
  471.  
  472. fixed()
  473. {
  474.     register int    i;
  475.     int             r, g, b;
  476.  
  477.     printf("Using fixed palette %d, ", fixed_pal);
  478.     switch(fixed_pal) {
  479.         case 0: printf("grey scale.\n");
  480.             for(i=0; i<256; i++) {
  481.                 red[i] = i>>2;
  482.                 grn[i] = i>>2;
  483.                 blu[i] = i>>2;
  484.             }
  485.             break;
  486.         case 1: printf("8 red * 8 green * 4 blue shades.\n");
  487.             for(i=0; i<256; i++) {
  488.                 red[i] = (i>>5)*63, red[i] /= 7;
  489.                 grn[i] = ((i>>2)&0x07)*63, grn[i] /= 7;
  490.                 blu[i] = (i&0x03)*63, blu[i] /= 3;
  491.             }
  492.             break;
  493.         case 2: printf("6 red * 7 green * 6 blue shades.\n");
  494.             for(b=0; b<6; b++)
  495.                 for(g=0; g<7; g++)
  496.                     for(r=0; r<6; r++) {
  497.                         i = r*42 + g*6 + b;
  498.                         red[i] = r*63/5;
  499.                         grn[i] = g*63/6;
  500.                         blu[i] = b*63/5;
  501.                     }
  502.             break;
  503.         default:
  504.             printf("Error, palette choice not valid\n");
  505.             printf("Valid choices are 0..2.\n");
  506.             exit(1);
  507.     }       /* end of switch */
  508. }       /* end of fixed */
  509.  
  510. /*
  511.     m_box() -- choose palette by median cut using boxes
  512. */
  513.  
  514. Box     box[256];
  515.  
  516. m_box()
  517. {
  518.     int     i, j, max, dr, dg, db;
  519.  
  520.     /* force the counts in the corners to be zero */
  521.  
  522.     force( 0,  0,  0, 0);
  523.     force(63,  0,  0, 0);
  524.     force( 0, 63,  0, 0);
  525.     force( 0,  0, 63, 0);
  526.     force(63, 63,  0, 0);
  527.     force( 0, 63, 63, 0);
  528.     force(63,  0, 63, 0);
  529.     force(63, 63, 63, 0);
  530.  
  531.     /* assign the 1st eight boxes to be the corners */
  532.     make_box( 0,  0,  0, 0, 1);
  533.     make_box(63,  0,  0, 1, 1);
  534.     make_box( 0, 63,  0, 2, 1);
  535.     make_box( 0,  0, 63, 3, 1);
  536.     make_box(63, 63,  0, 4, 1);
  537.     make_box( 0, 63, 63, 5, 1);
  538.     make_box(63,  0, 63, 6, 1);
  539.     make_box(63, 63, 63, 7, 1);
  540.  
  541.     /* set up 9th box to hold the rest of the world */
  542.     box[8].r0 = 0;
  543.     box[8].r1 = 63;
  544.     box[8].g0 = 0;
  545.     box[8].g1 = 63;
  546.     box[8].b0 = 0;
  547.     box[8].b1 = 63;
  548.     squeeze(8);
  549.  
  550.     /* split the rest of the boxes */
  551.  
  552.     printf("Choosing palette using median cut.\n");
  553.     printf("        Counting by pixel, limit = %u.\n", count_limit);
  554.     printf("        palette entry ");
  555.     for(i=9; i<256; i++) {
  556. #ifdef DEBUG
  557.         printf("\n");
  558.         for(j=0; j<i; j++)
  559.             printf("box %3d    %2d %2d %2ld  %2d %2d %2ld  %2d %2d %2ld    %5ld\n", j, box[j].r0, box[j].r1, box[j].rave, box[j].g0, box[j].g1, box[j].gave, box[j].b0, box[j].b1, box[j].bave, box[j].count);
  560. #endif
  561.         printf("%3d\b\b\b", i+1);
  562.         /* find biggest box */
  563.         max = 8;
  564.         for(j=8; j<i; j++)
  565.             if(box[j].count > box[max].count)
  566.                 max = j;
  567.  
  568.         /* decide which side to split the box along, and split it */
  569.  
  570.         dr = box[max].r1 - box[max].r0;
  571.         dg = box[max].g1 - box[max].g0;
  572.         db = box[max].b1 - box[max].b0;
  573.         box[i] = box[max];              /* copy info over */
  574.         if(dr>=dg && dr>=db) {          /* red! */
  575.             if(dr==2) {             /* tight squeeze */
  576.                 box[i].r1 = box[i].r0;
  577.                 box[max].r0 = box[max].r1;
  578.             } else {                /* figure out where to split */
  579.                 j = box[max].rave;
  580.                 if(j==box[max].r1)
  581.                     j--;
  582.                 box[max].r1 = j;
  583.                 box[i].r0 = j+1;
  584.             }
  585.             squeeze(i);
  586.             squeeze(max);
  587.         } else if(dg>=db) {             /* green! */
  588.             if(dg==2) {             /* tight squeeze */
  589.                 box[i].g1 = box[i].g0;
  590.                 box[max].g0 = box[max].g1;
  591.             } else {                /* figure out where to split */
  592.                 j = box[max].gave;
  593.                 if(j==box[max].g1)
  594.                     j--;
  595.                 box[max].g1 = j;
  596.                 box[i].g0 = j+1;
  597.             }
  598.             squeeze(i);
  599.             squeeze(max);
  600.         } else {                        /* blue! */
  601.             if(db==2) {             /* tight squeeze */
  602.                 box[i].b1 = box[i].b0;
  603.                 box[max].b0 = box[max].b1;
  604.             } else {                /* figure out where to split */
  605.                 j = box[max].bave;
  606.                 if(j==box[max].b1)
  607.                     j--;
  608.                 box[max].b1 = j;
  609.                 box[i].b0 = j+1;
  610.             }
  611.             squeeze(i);
  612.             squeeze(max);
  613.         }
  614.  
  615.     }       /* end of i loop, all the boxes are found */
  616.  
  617.     printf("\n");
  618.  
  619.     /* get palette colors for each box */
  620.     for(i=0; i<256; i++) {
  621.          red[i] = (box[i].r0+box[i].r1)/2;
  622.          grn[i] = (box[i].g0+box[i].g1)/2;
  623.          blu[i] = (box[i].b0+box[i].b1)/2;
  624.     }
  625.  
  626.     /* fix *8 palette for gif encoding */
  627.     for(i=0; i<256; i++) {
  628.         red8[i] = red[i]*255, red8[i] /= 63;
  629.         grn8[i] = grn[i]*255, grn8[i] /= 63;
  630.         blu8[i] = blu[i]*255, blu8[i] /= 63;
  631.     }
  632.  
  633. }       /* end of m_box() */
  634.  
  635. /*
  636.     make_box -- make a 1x1x1 box at index with color rgb count c
  637. */
  638.  
  639. make_box(r, g, b, index, c)
  640.     int     r, g, b, index, c;
  641. {
  642.     box[index].r0 = r;
  643.     box[index].r1 = r;
  644.     box[index].g0 = g;
  645.     box[index].g1 = g;
  646.     box[index].b0 = b;
  647.     box[index].b1 = b;
  648.     box[index].count = c;
  649. }       /* end of make_box
  650.  
  651. /*
  652.     squeeze -- shrink a boxes extremes to fit tightly
  653.  
  654.            if a box is 1x1x1 change its count to 1
  655. */
  656.  
  657. squeeze(b)
  658.     int     b;      /* the box to put the squeeze on */
  659. {
  660.     int     r0, r1, g0, g1, b0, b1;
  661.     long    i, j, count = 0;
  662.     Node    *ptr;
  663.  
  664.     r0 = box[b].r0;
  665.     r1 = box[b].r1;
  666.     g0 = box[b].g0;
  667.     g1 = box[b].g1;
  668.     b0 = box[b].b0;
  669.     b1 = box[b].b1;
  670.  
  671.     box[b].r0 = 63; box[b].r1 = 0;
  672.     box[b].g0 = 63; box[b].g1 = 0;
  673.     box[b].b0 = 63; box[b].b1 = 0;
  674.     box[b].rave = 0;
  675.     box[b].gave = 0;
  676.     box[b].bave = 0;
  677.  
  678.     for(i=r0; i<=r1; i++)
  679.         for(j=g0; j<=g1; j++) {
  680.             ptr = grid[i][j];
  681.             while(ptr) {
  682.                 if(ptr->color > b1) {
  683.                     ptr = NULL;
  684.                 } else {
  685.                     if(ptr->color>=b0 && ptr->count>0L) {
  686.                         box[b].r0 = MIN(i, box[b].r0);
  687.                         box[b].r1 = MAX(i, box[b].r1);
  688.                         box[b].g0 = MIN(j, box[b].g0);
  689.                         box[b].g1 = MAX(j, box[b].g1);
  690.                         box[b].b0 = MIN(ptr->color, box[b].b0);
  691.                         box[b].b1 = MAX(ptr->color, box[b].b1);
  692.                         box[b].rave += (long)i * (long)ptr->count;
  693.                         box[b].gave += (long)j * (long)ptr->count;
  694.                         box[b].bave += (long)ptr->color * (long)ptr->count;
  695.                         count += (long)ptr->count;
  696.                     }
  697.                     ptr = ptr->next;
  698.                 }
  699.             }
  700.         }
  701.     /* box is now shrunk */
  702.  
  703.     if(count) {
  704.         box[b].rave /= count;
  705.         box[b].gave /= count;
  706.         box[b].bave /= count;
  707.     }
  708.  
  709.     box[b].count = MIN(count, count_limit);
  710.  
  711.     if(box[b].r0 == box[b].r1 &&
  712.        box[b].g0 == box[b].g1 &&
  713.        box[b].b0 == box[b].b1) {    /* box is min size */
  714.         box[b].count = 1;       /* so it won't get split again */
  715.     }
  716.  
  717. }       /* end of squeeze */
  718.  
  719.  
  720. /*
  721.     usage -- tell them how its done
  722. */
  723.  
  724. usage(name)
  725.     char    *name;          /* av(0) */
  726. {
  727.    fprintf(stdout, "Version 2.0            Copyright 1990-1992 Stephen B. Coy\n");
  728.    fprintf(stdout, "                       TGA mods by Drew Wells\n");
  729.    fprintf(stdout, "Usage:  %s [-d] [-o] [-r (#)] [-m (#)] [-f (#)] [-p pal_file] <file>\n\n", name);
  730.    fprintf(stdout, "where -d    use Floyd Steinberg dithering\n");
  731.    fprintf(stdout, "      -o    use ordered dithering\n");
  732.    fprintf(stdout, "      -r #  add random noise +- #\n");
  733.    fprintf(stdout, "            defaults to +-%d if # not given\n", DEF_NOISE);
  734.    fprintf(stdout, "      -m    choose palette with median cut\n");
  735.    fprintf(stdout, "            defaults to popularity\n");
  736.    fprintf(stdout, "      -m #  limit median cut pixel count to #\n");
  737.    fprintf(stdout, "      -f #  use a fixed palette, fast but (sometimes) ugly\n");
  738.    fprintf(stdout, "            # determines which palette to use\n");
  739.    fprintf(stdout, "            0 == grey scale\n");
  740.    fprintf(stdout, "            1 == 8 red * 8 green * 4 blue shades\n");
  741.    fprintf(stdout, "            2 == 6 red * 7 green * 6 blue shades\n");
  742.    fprintf(stdout, "      -p <pal_file>  if pal_file exists use it\n");
  743.    fprintf(stdout, "            as the source of the palette, if it\n");
  744.    fprintf(stdout, "            doesn't exist, create it with the new palette\n");
  745.  
  746.     exit(1);
  747. }
  748.  
  749. /*
  750.     my_calloc
  751. */
  752.  
  753. #define CHUNK           (32000)
  754. #define MIN_SIZE        (1024)
  755.  
  756. void    *my_calloc(n)
  757.     int     n;      /* how many bytes */
  758. {
  759.     static char             *ptr = NULL;
  760.     char                    *ret;
  761.     static unsigned int     bytes_left = 0;
  762.  
  763.     if(n > bytes_left) {            /* we need more RAM */
  764.         ptr = calloc(CHUNK, 1);
  765.         if(ptr==NULL) {         /* squeeze every last bit */
  766.             ret = calloc(n, 1);
  767.             if(ret) {
  768.                 return ret;
  769.             }
  770.             if(last_pass) {
  771.                 return NULL;
  772.             }
  773.          fprintf(stderr, "\nError, not enough RAM.\n");
  774.             exit(1);
  775.         }
  776.         bytes_left = CHUNK;
  777.     }
  778.     ret = ptr;
  779.     ptr += n;
  780.     bytes_left -= n;
  781.  
  782.     return ret;
  783. }       /* my_calloc() */
  784.  
  785.  
  786. /*
  787.     add_color -- add a color to the tree (or at least up its count)
  788. */
  789.  
  790. add_color(r, g, b, c)
  791.     int     r, g, b,        /* color to add to tree */
  792.         c;              /* number of pixels */
  793. {
  794.     Node    *ptr, *prev;
  795.     void    *my_calloc();
  796.     long    ltmp;
  797.  
  798.     c = MIN(c, count_limit);
  799.  
  800.     ptr = grid[r][g];
  801.     prev = ptr;
  802.     if(!ptr) {              /* new list */
  803.         ptr = (Node *)my_calloc(sizeof(Node));
  804.         grid[r][g] = ptr;
  805.         ptr->color = b;
  806.         ptr->count = (unsigned int)c;
  807.         ptr->next = NULL;
  808.         total_colors++;
  809.  
  810.         return 0;
  811.     }
  812.     if(ptr->color > b) {    /* need a new node at the head */
  813.         prev = (Node *)my_calloc(sizeof(Node));
  814.         prev->color = b;
  815.         prev->count = (unsigned int)c;
  816.         prev->next = ptr;
  817.         grid[r][g] = prev;
  818.         total_colors++;
  819.  
  820.         return 0;
  821.     }
  822.  
  823.     for(;;) {       /* walk down the list looking for the right place */
  824.         if(ptr->color == b) {
  825.             ltmp = ptr->count;
  826.             ltmp += (unsigned int)c;
  827.             ltmp = MIN(ltmp, count_limit);
  828.             ptr->count = (unsigned int)ltmp;
  829.  
  830.             return 0;
  831.         }
  832.         if(ptr->next == (Node *)NULL) {     /* end of the rope */
  833.             ptr->next = (Node *)my_calloc(sizeof(Node));
  834.             ptr = ptr->next;
  835.             ptr->color = b;
  836.             ptr->count = (unsigned int)c;
  837.             ptr->next = NULL;
  838.             total_colors++;
  839.  
  840.             return 0;
  841.         }
  842.  
  843.         prev = ptr;             /* step down to next node */
  844.         ptr = ptr->next;
  845.     }       /* end of forever loop */
  846. }       /* end of add_color()*/
  847.  
  848. /*
  849.     get_index -- get the palette index of an rgb color
  850. */
  851.  
  852. get_index(r, g, b)
  853.     int     r, g, b;        /* color to find*/
  854. {
  855.     Node            *ptr, *prev;
  856.     void            *my_calloc();
  857.     unsigned short  color;
  858.  
  859.     if(method==FIXED) {
  860.         switch(fixed_pal) {
  861.             case 0: {
  862.                     long  i, j, k;
  863.                     i = r; j = g; k = b;
  864.                     r = (i*77+j*150+k*29)/64;
  865.                     return r;
  866.                 }
  867.                 break;
  868.             case 1: return ((r<<2)&0xe0) + ((g>>1)&0x1c) + ((b>>4)&0x03);
  869.                 break;
  870.             case 2: return ((6*r)/64)*42 + ((7*g)/64)*6 + ((6*b)/64);
  871.                 break;
  872.         }
  873.     }
  874.  
  875.     ptr = grid[r][g];
  876.     prev = ptr;
  877.     if(!ptr) {      /* no color so we must create one */
  878.         ptr = (Node *)my_calloc(sizeof(Node));
  879.         if(ptr) {
  880.             grid[r][g] = ptr;
  881.             color = map(r, g, b);
  882.             ptr->count = color;
  883.             ptr->color = b;
  884.             ptr->next = NULL;
  885.             total_colors++;
  886.         } else {
  887.             color = map(r, g, b);
  888.         }
  889.  
  890.         return color;
  891.     }
  892.     if(ptr->color > b) {    /* need a new node at the head */
  893.         prev = (Node *)my_calloc(sizeof(Node));
  894.         if(prev) {
  895.             color = map(r, g, b);
  896.             prev->count = color;
  897.             prev->color = b;
  898.             prev->next = ptr;
  899.             grid[r][g] = prev;
  900.             total_colors++;
  901.         } else {
  902.             color = map(r, g, b);
  903.         }
  904.  
  905.         return color;
  906.     }
  907.  
  908.     for(;;) {       /* walk down the list looking for the right color */
  909.         if(ptr->color == b) {
  910.             return ptr->count;
  911.         }
  912.         if(ptr->next == (Node *)NULL) {     /* end of the rope */
  913.             ptr->next = (Node *)my_calloc(sizeof(Node));
  914.             if(ptr->next) {
  915.                 ptr = ptr->next;
  916.                 ptr->color = b;
  917.                 color = map(r, g, b);
  918.                 ptr->count = color;
  919.                 ptr->next = NULL;
  920.                 total_colors++;
  921.             } else {
  922.                 color = map(r, g, b);
  923.             }
  924.  
  925.             return color;
  926.         }
  927.  
  928.         prev = ptr;             /* step down to next node */
  929.         ptr = ptr->next;
  930.     }       /* end of forever loop */
  931. }       /* end of get_index()*/
  932.  
  933. /*
  934.     force -- force a specific count on a color (if it exists)
  935. */
  936.  
  937. force(r, g, b, c)
  938.     int     r, g, b,        /* color to add to tree */
  939.         c;              /* count to force */
  940. {
  941.     Node    *ptr, *prev;
  942.     void    *my_calloc();
  943.     long    ltmp;
  944.  
  945.     ptr = grid[r][g];
  946.     prev = ptr;
  947.     if(!ptr) {              /* new list */
  948.         ptr = (Node *)my_calloc(sizeof(Node));
  949.         grid[r][g] = ptr;
  950.         ptr->color = b;
  951.         ptr->count = (unsigned int)c;
  952.         ptr->next = NULL;
  953.         total_colors++;
  954.  
  955.         return 0;
  956.     }
  957.     if(ptr->color > b) {    /* need a new node at the head */
  958.         prev = (Node *)my_calloc(sizeof(Node));
  959.         prev->color = b;
  960.         prev->count = (unsigned int)c;
  961.         prev->next = ptr;
  962.         grid[r][g] = prev;
  963.         total_colors++;
  964.  
  965.         return 0;
  966.     }
  967.  
  968.     for(;;) {       /* walk down the list looking for the right place */
  969.         if(ptr->color == b) {
  970.             ptr->count = (unsigned int)c;
  971.  
  972.             return 0;
  973.         }
  974.         if(ptr->next == (Node *)NULL) {     /* end of the rope */
  975.             ptr->next = (Node *)my_calloc(sizeof(Node));
  976.             ptr = ptr->next;
  977.             ptr->color = b;
  978.             ptr->count = (unsigned int)c;
  979.             ptr->next = NULL;
  980.             total_colors++;
  981.  
  982.             return 0;
  983.         }
  984.  
  985.         prev = ptr;             /* step down to next node */
  986.         ptr = ptr->next;
  987.     }       /* end of forever loop */
  988. }       /* end of force()*/
  989.  
  990.  
  991. /*
  992.     get_pix(x, y) -- return the palette index of x,y
  993. */
  994.  
  995. get_pix(x, y)
  996.     int     x, y;
  997. {
  998.     static int      pal, count=0, line = -1;
  999.     static int      c, r, g, b;
  1000.     int             r2, g2, b2;
  1001.  
  1002.     if(line == -1) {
  1003.         printf("        line ");
  1004.     }
  1005.     if(line != y) {
  1006.         line = y;
  1007.         if((line % PRINT_STEP) == 0)
  1008.             printf("%4d  colors %6lu\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b", line, total_colors);
  1009.     }
  1010.     if(count == 0) {
  1011.         count = 0; /* don't read count for TGA */
  1012.         if(count == -1)
  1013.             count = 1024;
  1014.         b = my_getc(infp);
  1015.         g = my_getc(infp);
  1016.         r = my_getc(infp);
  1017.         pal = get_index(r>>2, g>>2, b>>2);
  1018.     }
  1019.   else {
  1020.         count--;
  1021.     }
  1022.  
  1023.     if(noise) {
  1024.         r2 = r + rand()%noise - rand()%noise; r2 = CLIP(r2);
  1025.         g2 = g + rand()%noise - rand()%noise; g2 = CLIP(g2);
  1026.         b2 = b + rand()%noise - rand()%noise; b2 = CLIP(b2);
  1027.         pal = get_index(r2>>2, g2>>2, b2>>2);
  1028.     }
  1029.     if(ordered) {
  1030.         register int    scale;
  1031.  
  1032.         scale = fixed==0 ? 1 : 2;
  1033.         if(noise == 0) {
  1034.             r2 = r;
  1035.             g2 = g;
  1036.             b2 = b;
  1037.         }
  1038.         r2 += scale * ord_dith[x%4][y%4]; r2 = CLIP(r2);
  1039.         g2 += scale * ord_dith[x%4][y%4]; g2 = CLIP(g2);
  1040.         b2 += scale * ord_dith[x%4][y%4]; b2 = CLIP(b2);
  1041.         pal = get_index(r2>>2, g2>>2, b2>>2);
  1042.     }
  1043.  
  1044.     return pal;
  1045. }       /* end of get_pix() */
  1046.  
  1047.  
  1048.  
  1049. /*
  1050.     get_pix_fs -- get_pix that does fs dithering
  1051. */
  1052.  
  1053. get_pix_fs(x, y)
  1054.     int     x, y;
  1055. {
  1056.     int             i, j, r, g, b, c;
  1057.     int             rerr, gerr, berr;
  1058.     static int      *buf[2][3];             /* our buffer */
  1059.     static int      line = -1;
  1060.  
  1061.     if(line == -1) {
  1062.         /* allocate space for the buffer */
  1063.         for(i=0; i<2; i++)
  1064.             for(j=0; j<3; j++)
  1065.                 buf[i][j] = my_calloc((width+1)*sizeof(int));
  1066.         i = 0;                  /* read in scan line 0 */
  1067.         while(i<width) {
  1068.             c = 1;
  1069.             if(c==0)
  1070.                 c = 1024;
  1071.             b = my_getc(infp);
  1072.             g = my_getc(infp);
  1073.             r = my_getc(infp);
  1074.             rerr = r;
  1075.             gerr = g;
  1076.             berr = b;
  1077.             while(c) {
  1078.                 if(noise) {
  1079.                     rerr = r + rand()%noise - rand()%noise; rerr = CLIP(rerr);
  1080.                     gerr = g + rand()%noise - rand()%noise; gerr = CLIP(gerr);
  1081.                     berr = b + rand()%noise - rand()%noise; berr = CLIP(berr);
  1082.                 }
  1083.                 buf[line&0x01][0][i] = rerr;
  1084.                 buf[line&0x01][1][i] = gerr;
  1085.                 buf[line&0x01][2][i] = berr;
  1086.                 c--; i++;
  1087.             }
  1088.         }       /* we've got line 0 */
  1089.         printf("        dithering line ");
  1090.     }       /* end of initial setup */
  1091.  
  1092.     if(line != y) {         /* we're starting a new line */
  1093.         line = y;
  1094.         if((line % PRINT_STEP) == 0)
  1095.             printf("%4d  colors %6lu\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b", line, total_colors);
  1096.         if(y < height-1) {     /* if not at last scan line */
  1097.             i = 0;                  /* read in scan line y */
  1098.             while(i<width) {
  1099.                 c = 1;
  1100.                 if(c==0)
  1101.                     c = 1024;
  1102.                 b = my_getc(infp);
  1103.                 g = my_getc(infp);
  1104.                 r = my_getc(infp);
  1105.                 rerr = r;
  1106.                 gerr = g;
  1107.                 berr = b;
  1108.                 while(c) {
  1109.                     if(noise) {
  1110.                         rerr = r + rand()%noise - rand()%noise; rerr = CLIP(rerr);
  1111.                         gerr = g + rand()%noise - rand()%noise; gerr = CLIP(gerr);
  1112.                         berr = b + rand()%noise - rand()%noise; berr = CLIP(berr);
  1113.                     }
  1114.                     buf[line&0x01][0][i] = rerr;
  1115.                     buf[line&0x01][1][i] = gerr;
  1116.                     buf[line&0x01][2][i] = berr;
  1117.                     c--; i++;
  1118.                 }
  1119.             }       /* we've got line y in buf y%2 */
  1120.  
  1121.             j = (line+1)%2;
  1122.  
  1123.             /* dither buf (line+1)%2  ie j */
  1124.  
  1125.             if(j) {     /* alternate for serpentine */
  1126.                 for(i=1; i<width-1; i++) {
  1127.                     r = CLIP(buf[j][0][i]);
  1128.                     g = CLIP(buf[j][1][i]);
  1129.                     b = CLIP(buf[j][2][i]);
  1130.                     c = get_index(r>>2, g>>2, b>>2);
  1131.                     buf[j][0][i] = c;   /* put palette index back for output */
  1132.                     rerr = r - red8[c];
  1133.                     gerr = g - grn8[c];
  1134.                     berr = b - blu8[c];
  1135.                     if(rerr) {
  1136.                         buf[j][0][i+1] += rerr*7/16;
  1137.                         buf[y%2][0][i] += rerr*5/16;
  1138.                         buf[y%2][0][i+1] += rerr/16;
  1139.                         buf[y%2][0][i-1] += rerr*3/16;
  1140.                     }
  1141.                     if(gerr) {
  1142.                         buf[j][1][i+1] += gerr*7/16;
  1143.                         buf[y%2][1][i] += gerr*5/16;
  1144.                         buf[y%2][1][i+1] += gerr/16;
  1145.                         buf[y%2][1][i-1] += gerr*3/16;
  1146.                     }
  1147.                     if(berr) {
  1148.                         buf[j][2][i+1] += berr*7/16;
  1149.                         buf[y%2][2][i] += berr*5/16;
  1150.                         buf[y%2][2][i+1] += berr/16;
  1151.                         buf[y%2][2][i-1] += berr*3/16;
  1152.                     }
  1153.                 }   /* end of i loop */
  1154.                 /* fix first and last pixels in scan line */
  1155.                 i = 0;
  1156.                 r = CLIP(buf[j][0][i]);
  1157.                 g = CLIP(buf[j][1][i]);
  1158.                 b = CLIP(buf[j][2][i]);
  1159.                 c = get_index(r>>2, g>>2, b>>2);
  1160.                 buf[j][0][i] = c;
  1161.                 i = width-1;
  1162.                 r = CLIP(buf[j][0][i]);
  1163.                 g = CLIP(buf[j][1][i]);
  1164.                 b = CLIP(buf[j][2][i]);
  1165.                 c = get_index(r>>2, g>>2, b>>2);
  1166.                 buf[j][0][i] = c;
  1167.             } else {    /* else scan left */
  1168.                 for(i=width-2; i>0; i--) {
  1169.                     r = CLIP(buf[j][0][i]);
  1170.                     g = CLIP(buf[j][1][i]);
  1171.                     b = CLIP(buf[j][2][i]);
  1172.                     c = get_index(r>>2, g>>2, b>>2);
  1173.                     buf[j][0][i] = c;   /* put palette index back for output */
  1174.                     rerr = r - red8[c];
  1175.                     gerr = g - grn8[c];
  1176.                     berr = b - blu8[c];
  1177.                     if(rerr) {
  1178.                         buf[j][0][i-1] += rerr*7/16;
  1179.                         buf[y%2][0][i] += rerr*5/16;
  1180.                         buf[y%2][0][i-1] += rerr/16;
  1181.                         buf[y%2][0][i+1] += rerr*3/16;
  1182.                     }
  1183.                     if(gerr) {
  1184.                         buf[j][1][i-1] += gerr*7/16;
  1185.                         buf[y%2][1][i] += gerr*5/16;
  1186.                         buf[y%2][1][i-1] += gerr/16;
  1187.                         buf[y%2][1][i+1] += gerr*3/16;
  1188.                     }
  1189.                     if(berr) {
  1190.                         buf[j][2][i-1] += berr*7/16;
  1191.                         buf[y%2][2][i] += berr*5/16;
  1192.                         buf[y%2][2][i-1] += berr/16;
  1193.                         buf[y%2][2][i+1] += berr*3/16;
  1194.                     }
  1195.                 }   /* end of i loop */
  1196.                 /* fix first and last pixels in scan line */
  1197.                 i = 0;
  1198.                 r = CLIP(buf[j][0][i]);
  1199.                 g = CLIP(buf[j][1][i]);
  1200.                 b = CLIP(buf[j][2][i]);
  1201.                 c = get_index(r>>2, g>>2, b>>2);
  1202.                 buf[j][0][i] = c;
  1203.                 i = width-1;
  1204.                 r = CLIP(buf[j][0][i]);
  1205.                 g = CLIP(buf[j][1][i]);
  1206.                 b = CLIP(buf[j][2][i]);
  1207.                 c = get_index(r>>2, g>>2, b>>2);
  1208.                 buf[j][0][i] = c;
  1209.             }   /* end of right to left scan */
  1210.         } else {    /* we're at the last scan line */
  1211.             j = (line+1) & 0x01;
  1212.             /* just convert last line, no dithering */
  1213.             for(i=0; i<width; i++) {
  1214.                 r = CLIP(buf[j][0][i]);
  1215.                 g = CLIP(buf[j][1][i]);
  1216.                 b = CLIP(buf[j][2][i]);
  1217.                 c = get_index(r>>2, g>>2, b>>2);
  1218.                 buf[j][0][i] = c;
  1219.             }
  1220.         }
  1221.     }       /* end of if at beginning of new line */
  1222.  
  1223.     /* output appropriate pixel value from buf */
  1224.  
  1225.     c = buf[(line+1)&0x01][0][x];
  1226.     if(c>255 || c<0) {
  1227.       fprintf(stderr, "Oops, trying to pass off %d as a valid color @ %d %d.\n", c, x, y);
  1228.         c = CLIP(c);
  1229.     }
  1230.     return c;
  1231.  
  1232. }       /* end of get_pix_fs() */
  1233.  
  1234.  
  1235. /*
  1236.     map -- find the "best" mapping of an rgb value in the palette
  1237. */
  1238.  
  1239. map(r, g, b)
  1240.     int     r, g, b;
  1241. {
  1242.     int     i, j, k;
  1243.     int     dr, dg, db, c;
  1244.     int     best;
  1245.     long    min_dist, dist;
  1246.  
  1247.     best = 0;
  1248.     i = red[best];
  1249.     j = grn[best];
  1250.     k = blu[best];
  1251.     dr = i - r;
  1252.     dg = j - g;
  1253.     db = k - b;
  1254.     min_dist = (long)dr*(long)dr + (long)dg*(long)dg + (long)db*(long)db;
  1255.     for(c=1; c<256; c++) {
  1256.         i = red[c];
  1257.         j = grn[c];
  1258.         k = blu[c];
  1259.         dr = i - r;
  1260.         dg = j - g;
  1261.         db = k - b;
  1262.         dist = (long)dr*(long)dr + (long)dg*(long)dg + (long)db*(long)db;
  1263.         if(dist<min_dist) {
  1264.             min_dist = dist;
  1265.             best = c;
  1266.         }
  1267.     }
  1268.     return best;
  1269. }
  1270.  
  1271. /*
  1272.     remap_all -- find the palette mapping for the whole tree
  1273. */
  1274.  
  1275. remap_all()
  1276. {
  1277.     register int    r, g;
  1278.     unsigned long   colors;
  1279.     Node            *ptr;
  1280.  
  1281.     colors = total_colors;
  1282.     printf("Remapping tree to palette.\n        colors to go = ");
  1283.     for(r=0; r<RES; r++)
  1284.         for(g=0; g<RES; g++) {
  1285.             ptr = grid[r][g];
  1286.             while(ptr) {
  1287.                 ptr->count = map(r, g, ptr->color);
  1288.                 ptr = ptr->next;
  1289.                 --colors;
  1290.                 if((colors % (PRINT_STEP<<1)) == 0)
  1291.                     printf("%8lu\b\b\b\b\b\b\b\b", colors);
  1292.             }
  1293.         }
  1294.     printf("%8lu\b\b\b\b\b\b\b\b", colors);
  1295.     printf("\n");
  1296. }       /* end of remap_all */
  1297.  
  1298.  
  1299. /*****************************************************************************
  1300.     here and beyond there be dragons...
  1301. ******************************************************************************/
  1302.  
  1303. /*****************************************************************************
  1304.  *
  1305.  * GIFENCODE.C    - GIF Image compression interface
  1306.  *
  1307.  * GIFEncode( FName, GHeight, GWidth, GInterlace, Background,
  1308.  *          BitsPerPixel, Red, Green, Blue, GetPixel )
  1309.  *
  1310.  *****************************************************************************/
  1311.  
  1312.  
  1313. #define TRUE 1
  1314. #define FALSE 0
  1315.  
  1316. static int Width, Height;
  1317. static int curx, cury;
  1318. static long CountDown;
  1319. static int Pass = 0;
  1320. static int Interlace;
  1321.  
  1322. /*
  1323.  * Bump the 'curx' and 'cury' to point to the next pixel
  1324.  */
  1325. static
  1326. BumpPixel()
  1327. {
  1328.     /*
  1329.      * Bump the current X position
  1330.      */
  1331.     curx++;
  1332.  
  1333.     /*
  1334.      * If we are at the end of a scan line, set curx back to the beginning
  1335.      * If we are interlaced, bump the cury to the appropriate spot,
  1336.      * otherwise, just increment it.
  1337.      */
  1338.     if( curx == Width ) {
  1339.         curx = 0;
  1340.  
  1341.             if( !Interlace )
  1342.             cury++;
  1343.         else {
  1344.              switch( Pass ) {
  1345.  
  1346.                    case 0:
  1347.                       cury += 8;
  1348.                       if( cury >= Height ) {
  1349.                   Pass++;
  1350.                 cury = 4;
  1351.                 }
  1352.                           break;
  1353.  
  1354.                    case 1:
  1355.                       cury += 8;
  1356.                       if( cury >= Height ) {
  1357.                   Pass++;
  1358.                 cury = 2;
  1359.                 }
  1360.               break;
  1361.  
  1362.                    case 2:
  1363.                       cury += 4;
  1364.                       if( cury >= Height ) {
  1365.                          Pass++;
  1366.                          cury = 1;
  1367.                       }
  1368.                       break;
  1369.  
  1370.                    case 3:
  1371.                       cury += 2;
  1372.                       break;
  1373.             }
  1374.         }
  1375.     }
  1376. }
  1377.  
  1378. /*
  1379.  * Return the next pixel from the image
  1380.  */
  1381. GIFNextPixel( getpixel )
  1382. ifunptr getpixel;
  1383. {
  1384.     int r;
  1385.  
  1386.     if( CountDown == 0 )
  1387.         return EOF;
  1388.  
  1389.     CountDown--;
  1390.  
  1391.     r = ( * getpixel )( curx, cury );
  1392.  
  1393.     BumpPixel();
  1394.  
  1395.     return r;
  1396. }
  1397.  
  1398. /* public */
  1399.  
  1400. GIFEncode( FName, GWidth, GHeight, GInterlace, Background,
  1401.        BitsPerPixel, Red, Green, Blue, GetPixel )
  1402.  
  1403. char *FName;
  1404. int GWidth, GHeight;
  1405. int GInterlace;
  1406. int Background;
  1407. int BitsPerPixel;
  1408. int Red[], Green[], Blue[];
  1409. ifunptr GetPixel;
  1410.  
  1411. {
  1412.     FILE *fp;
  1413.     int B;
  1414.     int RWidth, RHeight;
  1415.     int LeftOfs, TopOfs;
  1416.     int Resolution;
  1417.     int ColorMapSize;
  1418.     int InitCodeSize;
  1419.     int i;
  1420.  
  1421.     Interlace = GInterlace;
  1422.  
  1423.     ColorMapSize = 1 << BitsPerPixel;
  1424.  
  1425.     RWidth = Width = GWidth;
  1426.     RHeight = Height = GHeight;
  1427.     LeftOfs = TopOfs = 0;
  1428.  
  1429.     Resolution = BitsPerPixel;
  1430.  
  1431.     /*
  1432.      * Calculate number of bits we are expecting
  1433.      */
  1434.     CountDown = (long)Width * (long)Height;
  1435.  
  1436.     /*
  1437.      * Indicate which pass we are on (if interlace)
  1438.      */
  1439.     Pass = 0;
  1440.  
  1441.     /*
  1442.      * The initial code size
  1443.      */
  1444.     if( BitsPerPixel <= 1 )
  1445.         InitCodeSize = 2;
  1446.     else
  1447.         InitCodeSize = BitsPerPixel;
  1448.  
  1449.     /*
  1450.      * Set up the current x and y position
  1451.      */
  1452.     curx = cury = 0;
  1453.  
  1454.     /*
  1455.      * Open the GIF file for binary write
  1456.      */
  1457.     fp = fopen( FName, "wb" );
  1458.  
  1459.     if( fp == (FILE *)0 ) {
  1460.         printf( "error: could not open output file\n" );
  1461.         exit(1);
  1462.     }
  1463.  
  1464.     /*
  1465.      * Write the Magic header
  1466.      */
  1467.     fwrite( "GIF87a", 1, 6, fp );
  1468.  
  1469.     /*
  1470.      * Write out the screen width and height
  1471.      */
  1472.     Putword( RWidth, fp );
  1473.     Putword( RHeight, fp );
  1474.  
  1475.     /*
  1476.      * Indicate that there is a global colour map
  1477.      */
  1478.     B = 0x80;    /* Yes, there is a color map */
  1479.  
  1480.     /*
  1481.      * OR in the resolution
  1482.      */
  1483.     B |= (Resolution - 1) << 5;
  1484.  
  1485.     /*
  1486.      * OR in the Bits per Pixel
  1487.      */
  1488.     B |= (BitsPerPixel - 1);
  1489.  
  1490.     /*
  1491.      * Write it out
  1492.      */
  1493.     fputc( B, fp );
  1494.  
  1495.     /*
  1496.      * Write out the Background colour
  1497.      */
  1498.     fputc( Background, fp );
  1499.  
  1500.     /*
  1501.      * Byte of 0's (future expansion)
  1502.      */
  1503.     fputc( 0, fp );
  1504.  
  1505.     /*
  1506.      * Write out the Global Colour Map
  1507.      */
  1508.          for( i=0; i<ColorMapSize; i++ ) {
  1509.         fputc( Red[i], fp );
  1510.         fputc( Green[i], fp );
  1511.         fputc( Blue[i], fp );
  1512.     }
  1513.  
  1514.     /*
  1515.      * Write an Image separator
  1516.      */
  1517.     fputc( ',', fp );
  1518.  
  1519.     /*
  1520.      * Write the Image header
  1521.      */
  1522.  
  1523.     Putword( LeftOfs, fp );
  1524.     Putword( TopOfs, fp );
  1525.     Putword( Width, fp );
  1526.     Putword( Height, fp );
  1527.  
  1528.     /*
  1529.      * Write out whether or not the image is interlaced
  1530.      */
  1531.     if( Interlace )
  1532.         fputc( 0x40, fp );
  1533.     else
  1534.         fputc( 0x00, fp );
  1535.  
  1536.     /*
  1537.      * Write out the initial code size
  1538.      */
  1539.     fputc( InitCodeSize, fp );
  1540.  
  1541.     /*
  1542.      * Go and actually compress the data
  1543.      */
  1544.     compress( InitCodeSize+1, fp, GetPixel );
  1545.  
  1546.     /*
  1547.      * Write out a Zero-length packet (to end the series)
  1548.      */
  1549.     fputc( 0, fp );
  1550.  
  1551.     /*
  1552.      * Write the GIF file terminator
  1553.      */
  1554.     fputc( ';', fp );
  1555.  
  1556.     /*
  1557.      * And close the file
  1558.      */
  1559.     fclose(fp);
  1560.  
  1561. }
  1562.  
  1563. /*
  1564.  * Write out a word to the GIF file
  1565.  */
  1566. static
  1567. Putword( w, fp )
  1568. int w;
  1569. FILE *fp;
  1570. {
  1571.     fputc( w & 0xff, fp );
  1572.     fputc( (w / 256) & 0xff, fp );
  1573. }
  1574.  
  1575. /***************************************************************************
  1576.  *
  1577.  *  GIFENCOD.C       - GIF Image compression routines
  1578.  *
  1579.  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
  1580.  *  David Rowley (mgardi@watdcsu.waterloo.edu)
  1581.  *
  1582.  ***************************************************************************/
  1583.  
  1584. /*
  1585.  * General DEFINEs
  1586.  */
  1587. #ifndef min
  1588. #define min(a,b)        ((a>b) ? b : a)
  1589. #endif
  1590.  
  1591. #define BITS    12
  1592. #define MSDOS   1
  1593.  
  1594. #define HSIZE  5003            /* 80% occupancy */
  1595.  
  1596. #ifdef NO_UCHAR
  1597.  typedef char   char_type;
  1598. #else
  1599.  typedef        unsigned char   char_type;
  1600. #endif /* UCHAR */
  1601.  
  1602. /*
  1603.  *
  1604.  * GIF Image compression - modified 'compress'
  1605.  *
  1606.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  1607.  *
  1608.  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  1609.  *              Jim McKie               (decvax!mcvax!jim)
  1610.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  1611.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  1612.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  1613.  *              Joe Orost               (decvax!vax135!petsd!joe)
  1614.  *
  1615.  */
  1616. #include <stdio.h>
  1617. #include <ctype.h>
  1618. #include <signal.h>
  1619.  
  1620. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  1621.  
  1622. static int n_bits;                        /* number of bits/code */
  1623. static int maxbits = BITS;                /* user settable max # bits/code */
  1624. static code_int maxcode;                  /* maximum code, given n_bits */
  1625. static code_int maxmaxcode = (code_int)1 << BITS; /* should NEVER generate this code */
  1626. #ifdef COMPATIBLE               /* But wrong! */
  1627. # define MAXCODE(n_bits)        ((code_int) 1 << (n_bits) - 1)
  1628. #else
  1629. # define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)
  1630. #endif /* COMPATIBLE */
  1631.  
  1632. static count_int htab [HSIZE];
  1633. static unsigned short codetab [HSIZE];
  1634. #define HashTabOf(i)       htab[i]
  1635. #define CodeTabOf(i)    codetab[i]
  1636.  
  1637. static code_int hsize = HSIZE;                 /* for dynamic table sizing */
  1638. static count_int fsize;
  1639.  
  1640. /*
  1641.  * To save much memory, we overlay the table used by compress() with those
  1642.  * used by decompress().  The tab_prefix table is the same size and type
  1643.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  1644.  * get this from the beginning of htab.  The output stack uses the rest
  1645.  * of htab, and contains characters.  There is plenty of room for any
  1646.  * possible stack (stack used to be 8000 characters).
  1647.  */
  1648.  
  1649. #define tab_prefixof(i) CodeTabOf(i)
  1650. #define tab_suffixof(i)        ((char_type *)(htab))[i]
  1651. #define de_stack               ((char_type *)&tab_suffixof((code_int)1<<BITS))
  1652.  
  1653. static code_int free_ent = 0;                  /* first unused entry */
  1654. static int exit_stat = 0;
  1655.  
  1656. /*
  1657.  * block compression parameters -- after all codes are used up,
  1658.  * and compression rate changes, start over.
  1659.  */
  1660. static int clear_flg = 0;
  1661.  
  1662. static int offset;
  1663. static long int in_count = 1;            /* length of input */
  1664. static long int out_count = 0;           /* # of codes output (for debugging) */
  1665.  
  1666. /*
  1667.  * compress stdin to stdout
  1668.  *
  1669.  * Algorithm:  use open addressing double hashing (no chaining) on the
  1670.  * prefix code / next character combination.  We do a variant of Knuth's
  1671.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  1672.  * secondary probe.  Here, the modular division first probe is gives way
  1673.  * to a faster exclusive-or manipulation.  Also do block compression with
  1674.  * an adaptive reset, whereby the code table is cleared when the compression
  1675.  * ratio decreases, but after the table fills.  The variable-length output
  1676.  * codes are re-sized at this point, and a special CLEAR code is generated
  1677.  * for the decompressor.  Late addition:  construct the table according to
  1678.  * file size for noticeable speed improvement on small files.  Please direct
  1679.  * questions about this implementation to ames!jaw.
  1680.  */
  1681.  
  1682. static int g_init_bits;
  1683. static FILE *g_outfile;
  1684.  
  1685. static int ClearCode;
  1686. static int EOFCode;
  1687.  
  1688. compress( init_bits, outfile, ReadValue )
  1689. int init_bits;
  1690. FILE *outfile;
  1691. ifunptr ReadValue;
  1692. {
  1693.     register long fcode;
  1694.     register code_int i = 0;
  1695.     register int c;
  1696.     register code_int ent;
  1697.     register code_int disp;
  1698.     register code_int hsize_reg;
  1699.     register int hshift;
  1700.  
  1701.     /*
  1702.      * Set up the globals:  g_init_bits - initial number of bits
  1703.      *                      g_outfile   - pointer to output file
  1704.      */
  1705.     g_init_bits = init_bits;
  1706.     g_outfile = outfile;
  1707.  
  1708.     /*
  1709.      * Set up the necessary values
  1710.      */
  1711.     offset = 0;
  1712.     out_count = 0;
  1713.     clear_flg = 0;
  1714.     in_count = 1;
  1715.     maxcode = MAXCODE(n_bits = g_init_bits);
  1716.  
  1717.     ClearCode = (1 << (init_bits - 1));
  1718.     EOFCode = ClearCode + 1;
  1719.     free_ent = ClearCode + 2;
  1720.  
  1721.     char_init();
  1722.  
  1723.     ent = GIFNextPixel( ReadValue );
  1724.  
  1725.     hshift = 0;
  1726.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  1727.     hshift++;
  1728.     hshift = 8 - hshift;                /* set hash code range bound */
  1729.  
  1730.     hsize_reg = hsize;
  1731.     cl_hash( (count_int) hsize_reg);            /* clear hash table */
  1732.  
  1733.     output( (code_int)ClearCode );
  1734.  
  1735. #ifdef SIGNED_COMPARE_SLOW
  1736.     while ( (c = GIFNextPixel( ReadValue )) != (unsigned) EOF ) {
  1737. #else
  1738.     while ( (c = GIFNextPixel( ReadValue )) != EOF ) {
  1739. #endif
  1740.  
  1741.     in_count++;
  1742.  
  1743.     fcode = (long) (((long) c << maxbits) + ent);
  1744.     i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
  1745.  
  1746.     if ( HashTabOf (i) == fcode ) {
  1747.         ent = CodeTabOf (i);
  1748.         continue;
  1749.     } else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  1750.         goto nomatch;
  1751.     disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  1752.     if ( i == 0 )
  1753.         disp = 1;
  1754. probe:
  1755.     if ( (i -= disp) < 0 )
  1756.         i += hsize_reg;
  1757.  
  1758.     if ( HashTabOf (i) == fcode ) {
  1759.         ent = CodeTabOf (i);
  1760.         continue;
  1761.     }
  1762.     if ( (long)HashTabOf (i) > 0 )
  1763.         goto probe;
  1764. nomatch:
  1765.     output ( (code_int) ent );
  1766.     out_count++;
  1767.     ent = c;
  1768. #ifdef SIGNED_COMPARE_SLOW
  1769.     if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
  1770. #else
  1771.     if ( free_ent < maxmaxcode ) {
  1772. #endif
  1773.         CodeTabOf (i) = free_ent++; /* code -> hashtable */
  1774.         HashTabOf (i) = fcode;
  1775.     } else
  1776.         cl_block();
  1777.     }
  1778.     /*
  1779.      * Put out the final code.
  1780.      */
  1781.     output( (code_int)ent );
  1782.     out_count++;
  1783.     output( (code_int) EOFCode );
  1784.  
  1785.     return 0;
  1786. }
  1787.  
  1788. /*****************************************************************
  1789.  * TAG( output )
  1790.  *
  1791.  * Output the given code.
  1792.  * Inputs:
  1793.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  1794.  *              that n_bits =< (long)wordsize - 1.
  1795.  * Outputs:
  1796.  *      Outputs code to the file.
  1797.  * Assumptions:
  1798.  *      Chars are 8 bits long.
  1799.  * Algorithm:
  1800.  *      Maintain a BITS character long buffer (so that 8 codes will
  1801.  * fit in it exactly).  Use the VAX insv instruction to insert each
  1802.  * code in turn.  When the buffer fills up empty it and start over.
  1803.  */
  1804.  
  1805. static unsigned long cur_accum = 0;
  1806. static int  cur_bits = 0;
  1807.  
  1808. static
  1809. unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  1810.                   0x001F, 0x003F, 0x007F, 0x00FF,
  1811.                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  1812.                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  1813.  
  1814. static
  1815. output( code )
  1816. code_int  code;
  1817. {
  1818.     cur_accum &= masks[ cur_bits ];
  1819.  
  1820.     if( cur_bits > 0 )
  1821.     cur_accum |= ((long)code << cur_bits);
  1822.     else
  1823.     cur_accum = code;
  1824.  
  1825.     cur_bits += n_bits;
  1826.  
  1827.     while( cur_bits >= 8 ) {
  1828.     char_out( (unsigned int)(cur_accum & 0xff) );
  1829.     cur_accum >>= 8;
  1830.     cur_bits -= 8;
  1831.     }
  1832.  
  1833.     /*
  1834.      * If the next entry is going to be too big for the code size,
  1835.      * then increase it, if possible.
  1836.      */
  1837.    if ( free_ent > maxcode || clear_flg ) {
  1838.  
  1839.         if( clear_flg ) {
  1840.  
  1841.         maxcode = MAXCODE (n_bits = g_init_bits);
  1842.         clear_flg = 0;
  1843.  
  1844.         } else {
  1845.  
  1846.         n_bits++;
  1847.         if ( n_bits == maxbits )
  1848.             maxcode = maxmaxcode;
  1849.         else
  1850.             maxcode = MAXCODE(n_bits);
  1851.         }
  1852.     }
  1853.  
  1854.     if( code == EOFCode ) {
  1855.     /*
  1856.      * At EOF, write the rest of the buffer.
  1857.      */
  1858.     while( cur_bits > 0 ) {
  1859.         char_out( (unsigned int)(cur_accum & 0xff) );
  1860.         cur_accum >>= 8;
  1861.         cur_bits -= 8;
  1862.     }
  1863.  
  1864.     flush_char();
  1865.  
  1866.     fflush( g_outfile );
  1867.  
  1868.     if( ferror( g_outfile ) )
  1869.         writeerr();
  1870.     }
  1871. }
  1872.  
  1873. /*
  1874.  * Clear out the hash table
  1875.  */
  1876. static
  1877. cl_block ()             /* table clear for block compress */
  1878. {
  1879.  
  1880.     cl_hash ( (count_int) hsize );
  1881.     free_ent = ClearCode + 2;
  1882.     clear_flg = 1;
  1883.  
  1884.     output( (code_int)ClearCode );
  1885. }
  1886.  
  1887. static
  1888. cl_hash(hsize)          /* reset code table */
  1889. register count_int hsize;
  1890. {
  1891.  
  1892.     register count_int *htab_p = htab+hsize;
  1893.  
  1894.     register long i;
  1895.     register long m1 = -1;
  1896.  
  1897.     i = hsize - 16;
  1898.     do {                            /* might use Sys V memset(3) here */
  1899.         *(htab_p-16) = m1;
  1900.         *(htab_p-15) = m1;
  1901.         *(htab_p-14) = m1;
  1902.         *(htab_p-13) = m1;
  1903.         *(htab_p-12) = m1;
  1904.         *(htab_p-11) = m1;
  1905.         *(htab_p-10) = m1;
  1906.         *(htab_p-9) = m1;
  1907.         *(htab_p-8) = m1;
  1908.         *(htab_p-7) = m1;
  1909.         *(htab_p-6) = m1;
  1910.         *(htab_p-5) = m1;
  1911.         *(htab_p-4) = m1;
  1912.         *(htab_p-3) = m1;
  1913.         *(htab_p-2) = m1;
  1914.         *(htab_p-1) = m1;
  1915.         htab_p -= 16;
  1916.     } while ((i -= 16) >= 0);
  1917.  
  1918.     for ( i += 16; i > 0; i-- )
  1919.         *--htab_p = m1;
  1920. }
  1921.  
  1922. static
  1923. writeerr()
  1924. {
  1925.     printf( "error writing output file\n" );
  1926.     exit(1);
  1927. }
  1928.  
  1929. /******************************************************************************
  1930.  *
  1931.  * GIF Specific routines
  1932.  *
  1933.  ******************************************************************************/
  1934.  
  1935. /*
  1936.  * Number of characters so far in this 'packet'
  1937.  */
  1938. static int a_count;
  1939.  
  1940. /*
  1941.  * Set up the 'byte output' routine
  1942.  */
  1943. static
  1944. char_init()
  1945. {
  1946.     a_count = 0;
  1947. }
  1948.  
  1949. /*
  1950.  * Define the storage for the packet accumulator
  1951.  */
  1952. static char accum[ 256 ];
  1953.  
  1954. /*
  1955.  * Add a character to the end of the current packet, and if it is 254
  1956.  * characters, flush the packet to disk.
  1957.  */
  1958. static
  1959. char_out( c )
  1960. int c;
  1961. {
  1962.     accum[ a_count++ ] = c;
  1963.     if( a_count >= 254 )
  1964.         flush_char();
  1965. }
  1966.  
  1967. /*
  1968.  * Flush the packet to disk, and reset the accumulator
  1969.  */
  1970. static
  1971. flush_char()
  1972. {
  1973.     if( a_count > 0 ) {
  1974.         fputc( a_count, g_outfile );
  1975.         fwrite( accum, 1, a_count, g_outfile );
  1976.         a_count = 0;
  1977.     }
  1978. }
  1979.  
  1980. /* The End */